// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
// 
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to flush it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.
// 
// The implementation uses three state flags internally:
// * B_BUSY: the block has been returned from bread
//     and has not been passed back to brelse.  
// * B_VALID: the buffer data has been initialized
//     with the associated disk block contents.
// * B_DIRTY: the buffer data has been modified
//     and needs to be written to disk.

#include "types.h"
#include "defs.h"
#include "param.h"
#include "spinlock.h"
#include "buf.h"

#define PGSIZEK	4096

void updateAnchorTable(struct buf * b);
void printAnchorTable(void);
int findEmptyInoderef();
struct inoderef * getiref(uint dev, int inum);
struct buf * allocateFreshBlock(int flag, uint dev, uint sector, int inum);
void printCountTbl(void);


struct {
	struct spinlock lock;
	struct buf buf[NBUF];

	// Linked list of all buffers, through prev/next.
	// head.next is most recently used.
	struct buf head;
} bcache;

struct buf * anchorTable[HASHPARAM];
struct inoderef inodeCountTable[NBUF];

void
binit(void)
{
	struct buf *b;

	initlock(&bcache.lock, "bcache");


	// Create linked list of buffers
	bcache.head.prev = &bcache.head;
	bcache.head.next = &bcache.head;
	bcache.head.bucketNext = 0;
	//bcache.head.bucketPrev = 0;
	for(b = bcache.buf; b < bcache.buf+NBUF; b++){
		b->next = bcache.head.next;
		b->prev = &bcache.head;
		//b->bucketPrev = 0;
		b->bucketNext = 0;
		b->dev = -1;
		b->inum = -1;
		bcache.head.next->prev = b;
		bcache.head.next = b;
	}

	cprintf("binit done\n");
}


// the method gets the device number and the sector key and returns the corresponding hash
// value. (index in the anchor table.
uint getHashValue(uint dev, uint sec){
	return  (((dev+1)*sec)%HASHPARAM);
}


// Look through buffer cache for sector on device dev.
// If not found, allocate fresh block.
// In either case, return locked buffer.
/***
static struct buf*
bget(uint dev, uint sector, int inum)
{
	struct buf *b;

	acquire(&bcache.lock);

	loop:
	// Try for cached block.
	for(b = bcache.head.next; b != &bcache.head; b = b->next){
		if(b->dev == dev && b->sector == sector){
			if(!(b->flags & B_BUSY)){
				b->flags |= B_BUSY;
				release(&bcache.lock);
				return b;
			}
			sleep(b, &bcache.lock);
			goto loop;
		}
	}

	// Allocate fresh block.
	for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
		if((b->flags & B_BUSY) == 0){
			b->dev = dev;
			b->sector = sector;
			b->inum = inum;
			b->flags = B_BUSY;
			release(&bcache.lock);

#if SRPPRINT==2
			cachePrint();
#endif

			return b;
		}
	}
	panic("bget: no buffers");
}
 ***/


static struct buf*
bget(uint dev, uint sector, int inum)
{
	struct buf *b;
	//uint hidx;
	int i;
	struct inoderef * iref;

	acquire(&bcache.lock);


	loop:
	// Try for cached block.

	for(b = anchorTable[getHashValue(dev,sector)]; b !=0 ; b = b->bucketNext){

		if(b->dev == dev && b->sector == sector){
			if(!(b->flags & B_BUSY)){
				b->flags |= B_BUSY;
				release(&bcache.lock);
				return b;
			}
			sleep(b, &bcache.lock);
			goto loop;
		}
	}


	if(SRPFLAG ){
		// SRP active
		iref = getiref(dev, inum);

		if(iref){
			if (iref->count>=SRP){
				// inode has to many buf in cache.
				//cprintf("allocFB: 1\n");
				iref->count++;
				b =  allocateFreshBlock(1,dev,sector,inum);
				//printCountTbl();
				return b;
			}
			else{
				// we're within the SRP boundries, just allocate a new block for it.
				iref->count++;
				//cprintf("allocFB: 2\n");
				return allocateFreshBlock(0,dev,sector,inum);

			}
		}
		else{
			//cprintf("allocFB: 3\n");
			b = allocateFreshBlock(0,dev,sector,inum);
			i = findEmptyInoderef();
			inodeCountTable[i].count = 1;
			inodeCountTable[i].dev = dev;
			inodeCountTable[i].inum = inum;
			return b;
		}


	}
	else{
		// NO SRP
		// Allocate fresh block.
		return allocateFreshBlock(0,dev,sector,inum);
	}



	panic("bget: no buffers");
}



// Return a B_BUSY buf with the contents of the indicated disk sector.
struct buf*
bread(uint dev, uint sector, int inum)
{
	struct buf *b;

	b = bget(dev, sector, inum);
	if(!(b->flags & B_VALID))
		iderw(b);
	return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
	if((b->flags & B_BUSY) == 0)
		panic("bwrite");
	b->flags |= B_DIRTY;
	iderw(b);
}

// Release the buffer b.
void
brelse(struct buf *b)
{

	if((b->flags & B_BUSY) == 0)
		panic("brelse");

	acquire(&bcache.lock);

	b->next->prev = b->prev;
	b->prev->next = b->next;
	b->next = bcache.head.next;
	b->prev = &bcache.head;

	bcache.head.next->prev = b;
	bcache.head.next = b;

	b->flags &= ~B_BUSY;
	wakeup(b);

	release(&bcache.lock);
}

void cachePrint(uint dev,uint sec, int inum){
	struct buf *b;
	int i;

	initlock(&bcache.lock, "bcache");

	cprintf("BC = [ ");
	for(i =0 ; i < NBUF; i++){
		b = &bcache.buf[i];
		if (b && b->flags){
			if (dev==b->dev && inum==b->inum && sec==b->sector)
				cprintf("#");
			cprintf("<%d, %d, %d> ", b->dev, b->sector, b->inum);
		}

	}

	cprintf("]\n");

}


/***
 * Update anchor table bucket lists, prior to removal of b
 */
void updateAnchorTable(struct buf * b){

	struct buf * t;
	uint hidx;

	hidx = getHashValue(b->dev,b->sector);
	if (anchorTable[hidx]){ // do we even have a relevant bucket list
		if (anchorTable[hidx] == b) // first in bucket list
		{
			anchorTable[hidx] = b->bucketNext;
		}
		else {
			// b is not first
			for(t = anchorTable[hidx]; t!=0 && t->bucketNext!=b ; t = t->bucketNext)
				;
			if (t)
				t->bucketNext = b->bucketNext;
		}
		b->bucketNext=0;
	}

}

void printAnchorTable(){
	uint idx;

	for(idx =0; idx < HASHPARAM; idx++){
		cprintf("anchor[%d]=0x%x\n",idx,anchorTable[idx]);
	}
}

int findEmptyInoderef(){
	int f=0;
	int i;

	for (i = 0; i < NBUF;i++) {
		if (inodeCountTable[i].count == 0){
			f = 1;
			break;
		}
	}

	if (!f)
		panic("WONDER ERROR!\n");
	return i;
}


struct buf * allocateFreshBlock(int flag, uint dev, uint sector, int inum){
	struct buf * b,*x;
	uint hidx;
	struct inoderef * iref;

	//cprintf("dev %d inum %d\n",dev,inum);
	for(b = bcache.head.prev; b != &bcache.head; b = b->prev){

		if (flag && (b->dev!=dev || b->inum!=inum))
			continue;

		if((b->flags & B_BUSY) == 0){
			// Update structs regarding the old data (which will be overwritten)
			updateAnchorTable(b);
			if (SRPFLAG){
				if (b->flags & B_VALID){
					iref = getiref(b->dev,b->inum);
					if (iref && iref->count){
						//panic("allocateFreshBlock: negative counter value");
						iref->count--;
					}
					if (!iref){
						cachePrint(0,0,0);
						printCountTbl(); // DEBUG PRINTING
						panic("allocateFreshBlock: IMPOSSIBLE");
					}
				}

			}


			// Overwrite with new data
			b->dev = dev;
			b->sector = sector;
			b->flags = B_BUSY;
			b->inum = inum;

			// insert b to the hash bucket.
			hidx = getHashValue(b->dev,b->sector);

			if (anchorTable[hidx]==0){
				// no "bucket list", start one
				anchorTable[hidx] = b;
			}
			else{
				// list exists, run to the end and add b
				for(x = anchorTable[hidx]; x->bucketNext !=0 ; x = x->bucketNext)
					;

				x->bucketNext = b;
				b->bucketNext = 0;
				//b->bucketPrev = x;
			}
			release(&bcache.lock);
#if SRPPRINT==2
			cachePrint(dev,sector, inum);
#endif
			return b;
		}
	}
#if SRPPRINT==2
	cachePrint(dev,sector, inum);
#endif
	printCountTbl(); // DEBUG PRINTING
	panic("allocateFreshBlock: no buffers");
	return 0;
}

struct inoderef * getiref(uint dev, int inum){
	struct inoderef * ir;
	int i;

	for(i = 0; i < NBUF; ++i){
		ir = &inodeCountTable[i];
		if (ir->dev==dev && ir->inum==inum)
			return ir;
	}

	return 0;
}

void printCountTbl(void){
	struct inoderef * ir;
	int i;

	cprintf("#### inodeColuntTable:\n");
	for(i = 0; i < NBUF; ++i){
		ir = &inodeCountTable[i];
		cprintf("dev=%d inum=%d count=%d\n",ir->dev,ir->inum,ir->count);
	}
	cprintf("#####################\n");

	return;
}
